{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reducing Dishes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSatisfaction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #做菜顺序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个厨师收集了他&nbsp;<code>n</code>&nbsp;道菜的满意程度&nbsp;<code>satisfaction</code>&nbsp;，这个厨师做出每道菜的时间都是 1 单位时间。</p>\n",
    "\n",
    "<p>一道菜的 「&nbsp;<strong>like-time 系数&nbsp;</strong>」定义为烹饪这道菜结束的时间（包含之前每道菜所花费的时间）乘以这道菜的满意程度，也就是&nbsp;<code>time[i]</code>*<code>satisfaction[i]</code>&nbsp;。</p>\n",
    "\n",
    "<p>返回厨师在准备了一定数量的菜肴后可以获得的最大 <strong>like-time 系数</strong> 总和。</p>\n",
    "\n",
    "<p>你可以按&nbsp;<strong>任意</strong>&nbsp;顺序安排做菜的顺序，你也可以选择放弃做某些菜来获得更大的总和。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>satisfaction = [-1,-8,0,5,-9]\n",
    "<strong>输出：</strong>14\n",
    "<strong>解释：</strong>去掉第二道和最后一道菜，最大的 like-time 系数和为 (-1*1 + 0*2 + 5*3 = 14) 。每道菜都需要花费 1 单位时间完成。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>satisfaction = [4,3,2]\n",
    "<strong>输出：</strong>20\n",
    "<strong>解释：可以</strong>按照任意顺序做菜 (2*1 + 3*2 + 4*3 = 20)\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>satisfaction = [-1,-4,-5]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>大家都不喜欢这些菜，所以不做任何菜就可以获得最大的 like-time 系数。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == satisfaction.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 500</code></li>\n",
    "\t<li><code>-1000 &lt;= satisfaction[i] &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reducing-dishes](https://leetcode.cn/problems/reducing-dishes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reducing-dishes](https://leetcode.cn/problems/reducing-dishes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-1,-8,0,5,-7]', '[4,3,2]', '[-1,-4,-5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        satisfaction.sort(reverse=True)\n",
    "        t = list(accumulate(satisfaction))\n",
    "        n = len(satisfaction)\n",
    "        ans = s = 0\n",
    "        for i in range(n):\n",
    "            s += t[i]\n",
    "            if ans < s: ans = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        # satisfaction.sort()\n",
    "        # n = len(satisfaction)\n",
    "        # a = [0]\n",
    "        # for i in range(1, n+1):\n",
    "        #     b = a + [-inf]\n",
    "        #     for t in range(i):\n",
    "        #         b[t+1] = a[t] + satisfaction[i-1]*(t+1)\n",
    "        #     a = b\n",
    "        # return max(a)\n",
    "\n",
    "        # -9 -8 -1 0 5\n",
    "        # 1\n",
    "        satisfaction.sort(reverse=True)\n",
    "        n = len(satisfaction)\n",
    "        ans = 0\n",
    "        for k in range(1, n+1):\n",
    "            res = 0\n",
    "            for i,j in zip(satisfaction, range(k, 0, -1)):\n",
    "                res += i * j\n",
    "            ans = max(ans, res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        ans = s = 0\n",
    "        for i, t in enumerate(accumulate(sorted(satisfaction, reverse=True))):\n",
    "            s += t\n",
    "            if ans < s: ans = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction):\n",
    "        satisfaction.sort()\n",
    "        if sum(satisfaction)>=0:\n",
    "            pass\n",
    "        else:\n",
    "            while sum(satisfaction)<0 and len(satisfaction):\n",
    "                satisfaction.pop(0)\n",
    "        res=0\n",
    "        for i in range(len(satisfaction)):\n",
    "            res += (i+1)*satisfaction[i]\n",
    " \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "      satisfaction.sort(reverse=True)\n",
    "      ans = 0\n",
    "      cur = 0\n",
    "      for s in satisfaction:\n",
    "        if s >= 0 or cur + s > 0:\n",
    "          ans += cur + s\n",
    "          cur += s\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        satisfaction.sort(key = lambda x : -x)\n",
    "        presum, ans = 0, 0\n",
    "        for si in satisfaction:\n",
    "            if presum + si > 0:\n",
    "                presum += si\n",
    "                ans += presum\n",
    "            else:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        satisfaction.sort()\n",
    "        max_ = 0\n",
    "        cnt = 0\n",
    "        r = len(satisfaction) - 1\n",
    "        while r >= 0:\n",
    "            cnt += sum(satisfaction[r::])\n",
    "            r -= 1\n",
    "            max_ = max(max_, cnt)\n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        satisfaction.sort()\n",
    "        print(f\"{satisfaction=}\")\n",
    "        n = len(satisfaction)\n",
    "\n",
    "        val = 0\n",
    "        for i, v in enumerate(satisfaction):\n",
    "            val += (i+1) * v\n",
    "        print(f\"{val=}\")\n",
    "\n",
    "        sum = [0] * (n+1)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            sum[i] = satisfaction[i] + sum[i+1]\n",
    "        print(f\"{sum=}\")\n",
    "\n",
    "        ans = max(0, val)\n",
    "        for i, v in enumerate(satisfaction):\n",
    "            val -= v + sum[i+1]\n",
    "            ans = max(ans, val)\n",
    "            print(f\"{i=} {val=}\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        if max(satisfaction) <= 0: return 0\n",
    "        list_len = len(satisfaction)\n",
    "        value = 0\n",
    "        positive_list = []\n",
    "        negative_list = []\n",
    "        for i in satisfaction:\n",
    "            if i >= 0:\n",
    "                positive_list.append(i)\n",
    "            else:\n",
    "                negative_list.append(i)\n",
    "        positive_value = sum(positive_list)\n",
    "        positive_list.sort()\n",
    "        negative_list.sort(reverse=True)\n",
    "        negative_data = 0\n",
    "        for i in range(len(negative_list)):\n",
    "            negative_data = negative_data + sum(negative_list[:i+1])\n",
    "            print(negative_data)\n",
    "            if (-sum(negative_list[:i+1])) < positive_value:\n",
    "                positive_list.insert(0, negative_list[i])\n",
    "            else:\n",
    "                break\n",
    "        index = 0\n",
    "        print(positive_list)\n",
    "        for i in positive_list:\n",
    "            index += 1\n",
    "            value = value + index * i\n",
    "        return value\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        satisfaction.sort()\n",
    "        list1=[]\n",
    "        a=0\n",
    "        b=0\n",
    "        for i in range(len(satisfaction)):\n",
    "            a=a+(i+1)*satisfaction[i]\n",
    "            print('a'+str(a))\n",
    "            if  satisfaction[i] < 0:\n",
    "                list1.append(satisfaction[i])\n",
    "        for j in range(len(list1)):\n",
    "            satisfaction.pop(0)\n",
    "            print(satisfaction)\n",
    "            for i in range(len(satisfaction)):\n",
    "                b=b+(i+1)*satisfaction[i]\n",
    "            a=max(a,b)\n",
    "            b=0\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        satisfaction.sort(reverse=True)\n",
    "        print(satisfaction)\n",
    "        res = [satisfaction[0]]\n",
    "        for i in range(1,len(satisfaction)+1):\n",
    "            res1 = 0\n",
    "            for j in range(i):\n",
    "                res1 += (i-j)*satisfaction[j]\n",
    "            res.append(max(res[i-1],res1))\n",
    "            print(res)\n",
    "        return max(max(res),0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        n = len(satisfaction) \n",
    "        satisfaction = SortedList(satisfaction)\n",
    "        if max(satisfaction) < 0:\n",
    "            return 0\n",
    "        elif min(satisfaction) > 0:\n",
    "            ans = 0\n",
    "            for i in range(1,n+1):\n",
    "                ans += satisfaction[i-1]*i\n",
    "            return ans\n",
    "        else:\n",
    "            temp = []\n",
    "            for i in range(1,n+1):\n",
    "                s = satisfaction[-i:]\n",
    "                a = 0\n",
    "                for j in range(1,i+1):\n",
    "                    a += s[j-1]*j\n",
    "                temp.append(a)\n",
    "            return max(temp)\n",
    "                  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        satisfaction.sort()\n",
    "        dp = [[0 for i in range(len(satisfaction)+1)] for j in range(len(satisfaction)+1)]\n",
    "        if satisfaction[-1] < 0:\n",
    "            return 0\n",
    "        for i in range(len(satisfaction)):\n",
    "            data = sum(satisfaction[-(i+1):])\n",
    "            dp[i+1] = dp[i]\n",
    "            dp[i+1][i+1] = data + dp[i][i]\n",
    "        return max(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        if len(satisfaction) == 1:\n",
    "            return max(satisfaction[0],0)\n",
    "        else:\n",
    "            satisfaction.sort()\n",
    "            time=[x for x in range(1,len(satisfaction)+1)]\n",
    "            like=sum([a*b for a,b in zip(time,satisfaction)])\n",
    "            if satisfaction[0] < 0:\n",
    "                temp=list(satisfaction)\n",
    "                temp.pop(0)\n",
    "                like=max(like,self.maxSatisfaction(temp))\n",
    "            return like"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        n = len(satisfaction)\n",
    "        satisfaction.sort()\n",
    "        pos, neg = [x for x in satisfaction if x >= 0] + [0], [x for x in satisfaction if x < 0]\n",
    "        # print(neg, pos)\n",
    "        maxv = sum(x * (i + 1) for i, x in enumerate(pos))\n",
    "        ret = sum(pos)\n",
    "        m = len(neg)\n",
    "        dp = [[-math.inf] * (m + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            dp[i + 1][1] = max(neg[i], maxv + ret + neg[i], dp[i][1])\n",
    "            for j in range(1, i + 1):\n",
    "                dp[i + 1][j + 1] = max(dp[i][j] + (j + 1) * neg[i] + ret, dp[i][j + 1], dp[i+1][j+1])\n",
    "        # print(dp)\n",
    "        return max(dp[-1] + [maxv])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        n = len(satisfaction)\n",
    "        satisfaction.sort()\n",
    "        pos, neg = [x for x in satisfaction if x >= 0] + [0], [x for x in satisfaction if x < 0]\n",
    "        # print(neg, pos)\n",
    "        maxv = sum(x * (i + 1) for i, x in enumerate(pos))\n",
    "        ret = sum(pos)\n",
    "        m = len(neg)\n",
    "        dp = [[-math.inf] * (m + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            dp[i + 1][1] = max(maxv + ret + neg[i], dp[i][1])\n",
    "            for j in range(1, i + 1):\n",
    "                dp[i + 1][j + 1] = max(dp[i][j] + (j + 1) * neg[i] + ret, dp[i][j + 1], dp[i+1][j+1])\n",
    "        # print(dp)\n",
    "        return max(dp[-1] + [maxv])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        n = len(satisfaction)\n",
    "        satisfaction.sort()\n",
    "        # dp[i][j]: 前 i 道，放弃 j 道的 最大总和\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        ans = 0\n",
    "        # 放弃做 j 道\n",
    "        for j in range(n):\n",
    "            # 从 j 开始做\n",
    "            total = 0\n",
    "            for i in range(j, n):\n",
    "                total += satisfaction[i] * (i - j + 1)\n",
    "            ans = max(ans, total)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        sort = sorted(satisfaction)\n",
    "        # f[i][j] j从0到i,前i个菜删除j个菜的最大的喜爱时间，因为是排好序的，所以删除一定发生在头部且连续\n",
    "        # f[i][j] = max(\n",
    "        #               f[i-1][j-1],  //i删除\n",
    "        #               f[i-1][j] + sort[i]*(i-j),  //i不删除，若存在\n",
    "        #               )\n",
    "        # max(f[len(sort)]) 即为所求\n",
    "\n",
    "        f = [[None for j in range(i+1)] for i in range(len(sort)+1)]\n",
    "        # f[i][0] 等于对应累加和\n",
    "        # f[i][i] = 0\n",
    "        f[1][0] = sort[0]\n",
    "        f[1][1] = 0\n",
    "        for i in range(2,len(sort)+1):\n",
    "            f[i][0] = f[i-1][0] + sort[i-1] * i\n",
    "            f[i][i] = 0\n",
    "        \n",
    "        for i in range(2,len(sort)+1):\n",
    "            for j in range(1,i):\n",
    "                f[i][j] = f[i-1][j-1]\n",
    "                if j <= i - 1:\n",
    "                    f[i][j] = max(f[i-1][j-1],f[i-1][j]+sort[i-1]*(i-j))\n",
    "        return max(f[len(sort)])\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        \n",
    "        satisfaction.sort()\n",
    "        # print(satisfaction)\n",
    "        l = []\n",
    "        for i in range(len(satisfaction)+1):\n",
    "            ll = []\n",
    "            for j in range(i+1):\n",
    "                ll.append(0)\n",
    "            l.append(ll)\n",
    "\n",
    "        # print(l)\n",
    "        for i in range(1,len(satisfaction)+1):\n",
    "            for j in range(i+1):\n",
    "                if j == 0:\n",
    "                    l[i][j] = 0\n",
    "                    continue\n",
    "                if j == i:\n",
    "                    l[i][j] = l[i-1][j-1] + j * satisfaction[i-1]\n",
    "                    continue\n",
    "                # 要\n",
    "                sy = l[i-1][j-1] + j * satisfaction[i-1]\n",
    "                # 不要\n",
    "                sn = l[i-1][j]\n",
    "                l[i][j] = max(sy,sn)\n",
    "                # print(l)\n",
    "        return max(l[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countAns(self,menu):\n",
    "        ans = 0\n",
    "        order = 1\n",
    "        for num in menu:\n",
    "            ans += num * order\n",
    "            order += 1\n",
    "        return ans\n",
    "\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        menu = satisfaction\n",
    "        positive = False\n",
    "        negative = False\n",
    "        zero = False\n",
    "        for num in menu:\n",
    "            if num == 0:\n",
    "                zero = True\n",
    "            elif num > 0:\n",
    "                positive = True\n",
    "            elif num < 0:\n",
    "                negative = True\n",
    "\n",
    "        # 全为正数或有0\n",
    "        if (positive or (positive and zero)) and negative == False:\n",
    "            menu.sort()\n",
    "            s = Solution()\n",
    "            res1 = s.countAns(menu)\n",
    "            menu.reverse()\n",
    "            res2 = s.countAns(menu)\n",
    "            return max(res1,res2)\n",
    "            \n",
    "        # 全为负数或有0\n",
    "        elif (negative or (negative and zero)) and positive == False:\n",
    "            return 0\n",
    "        # 有正有负或有0\n",
    "        else:\n",
    "            menu.sort()\n",
    "            # 分界点位置\n",
    "            tag = -1\n",
    "            # 标记是否做菜\n",
    "            isCook = True\n",
    "\n",
    "            # 标记分界点\n",
    "            for i in range(len(menu) - 1):\n",
    "                if menu[i] * menu[i + 1] <= 0:\n",
    "                    tag = i\n",
    "\n",
    "            temp = []\n",
    "            if isCook:\n",
    "                # 记录做菜最大值\n",
    "                while tag >= 0:\n",
    "                    ans = 0\n",
    "                    order = 1\n",
    "                    for i in range(tag, len(menu)):\n",
    "                        ans += menu[i] * order\n",
    "                        temp += [ans]\n",
    "                        order += 1\n",
    "                    tag -= 1\n",
    "\n",
    "                return max(temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.d = {}\n",
    "\n",
    "    def func(self,pretime,start,satisfaction):\n",
    "        if start==len(satisfaction):\n",
    "            return 0\n",
    "\n",
    "        rr = self.d.get((pretime,start))\n",
    "        if rr!=None:\n",
    "            return rr\n",
    "        if satisfaction[start]<0:\n",
    "            ret1 = (pretime+1)*satisfaction[start] + self.func(pretime+1,start+1,satisfaction)\n",
    "            ret2 = self.func(pretime,start+1,satisfaction)\n",
    "            ret = max(ret1,ret2)\n",
    "        else:\n",
    "            ret = 0\n",
    "            for i in range(start,len(satisfaction)):\n",
    "                ret += (pretime+1+i-start)*satisfaction[i]\n",
    "        self.d[(pretime,start)]=ret\n",
    "        return ret\n",
    "\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        satisfaction.sort()\n",
    "        return self.func(0,0,satisfaction)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        l=len(satisfaction)\n",
    "        satisfaction.sort()\n",
    "        dp=[[-float('inf')]*l for i in range(l)]\n",
    "        res=[satisfaction[0]]\n",
    "        for i in range(1,l):\n",
    "            res.append(res[-1]+(i+1)*satisfaction[i])\n",
    "        #print(res)\n",
    "        for i in range(l):\n",
    "            mid=res[::]\n",
    "            for j in range(i+1):\n",
    "                #print(i,res)\n",
    "                if j==0:\n",
    "                    dp[i][j]=satisfaction[i]\n",
    "                else:\n",
    "                    dp[i][j]=mid[j-1]+(j+1)*satisfaction[i]\n",
    "                res[j]=max(res[j],dp[i][j])\n",
    "        #print(res)\n",
    "        #print(dp)\n",
    "        return max(res) if max(res)>0 else 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        #dp[n][l]=dp[n-1][l]   dp[n-1][l-1]+n*l  \n",
    "        satisfaction=sorted(satisfaction)\n",
    "        n=len(satisfaction)\n",
    "        \n",
    "        dp=[[0]*(n) for i in range(n+1)]\n",
    "        \n",
    "        \n",
    "        dp[1][0]=satisfaction[0]\n",
    "        for i in range(1,n):\n",
    "            dp[1][i]=max(satisfaction[i],dp[1][i-1])\n",
    "            \n",
    "        \n",
    "            \n",
    "        \n",
    "        for i in range(2,n+1):\n",
    "            dp[i][i-1]=dp[i-1][i-2]+satisfaction[i-1]*i\n",
    "        \n",
    "    \n",
    "        #for r in dp:\n",
    "        #    print(r)\n",
    "            \n",
    "        #print()\n",
    "            \n",
    "        for i in range(2,n):\n",
    "            for j in range(i,n):\n",
    "                dp[i][j]=max(dp[i][j-1],dp[i-1][j-1]+satisfaction[j]*i)\n",
    "        \"\"\"        \n",
    "        for r in dp:\n",
    "            print(r)\n",
    "        \"\"\"\n",
    "        return max([max(r) for r in dp])\n",
    "    \n",
    "    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        # dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + j * satisfaction[i])\n",
    "        # 考虑到第i号菜，一共做了j道菜，所能得到的最大满意度（j <= i + 1）\n",
    "        n = len(satisfaction)\n",
    "        satisfaction.sort()\n",
    "        dp = [[0 for j in range(n + 1)] for i in range(n)]\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 2):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = 0\n",
    "                elif i == 0:\n",
    "                    dp[i][j] = j * satisfaction[i]\n",
    "                elif j <= i:\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + j * satisfaction[i])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + j * satisfaction[i]\n",
    "                if i == n - 1:\n",
    "                    ret = max(ret, dp[i][j])\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        n = len(satisfaction)\n",
    "        satisfaction = sorted(satisfaction)\n",
    "        dp = [[0] * (n+1) for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, i+1):\n",
    "                if i == j:\n",
    "                    dp[i][j] = dp[i-1][j-1] + j * satisfaction[i-1]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + j * satisfaction[i-1])\n",
    "        res = 0\n",
    "        for i in range(1, n+1):\n",
    "            res = max(res, dp[n][i])\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        satisfaction.sort() # 先排序\n",
    "        L = len(satisfaction)\n",
    "        res = 0 # 储存最大满意总和\n",
    "        dp = [[0] * L for _ in range(L)]\n",
    "        for i in range(L):\n",
    "            dp[i][i] = satisfaction[i]\n",
    "        for i in range(L):\n",
    "            for j in range(i + 1, L):\n",
    "                dp[i][j] = dp[i][j - 1] + satisfaction[j] * (j - i + 1)\n",
    "                res = max(res, dp[i][j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int: \n",
    "        num = len(satisfaction)\n",
    "        result = 0\n",
    "        satisfaction.sort()\n",
    "\n",
    "        dp = []\n",
    "        for _ in range(num+1):\n",
    "            temp = []\n",
    "            for _ in range(num+1):\n",
    "                temp.append(0)\n",
    "            dp.append(temp)\n",
    "            \n",
    "        dp[1][0] = 0\n",
    "        dp[1][1] = satisfaction[0]\n",
    "\n",
    "        for i in range(2, num+1):\n",
    "            for j in range(i+1):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = 0\n",
    "                elif j == i:\n",
    "                    dp[i][j] = dp[i-1][j-1] + satisfaction[i-1]*j\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + satisfaction[i - 1] * j)\n",
    "\n",
    "        for i in dp[num]:\n",
    "            result = max(result, i)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        n = len(satisfaction)\n",
    "        dp = [[0 for _ in range(n+1)] for _ in range(n+1)]\n",
    "        \n",
    "        satisfaction = sorted(satisfaction)\n",
    "        dp[0][1]=satisfaction[0]\n",
    "        for i in range(1,n):\n",
    "            dp[i][i+1]=dp[i-1][i]+satisfaction[i]*(i+1)\n",
    "        for i in range(1,n):\n",
    "            for j in range(1,i+1):\n",
    "                dp[i][j]=max(dp[i-1][j-1]+satisfaction[i]*j,dp[i-1][j])\n",
    "        return max(dp[n-1])\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        n = len(satisfaction)\n",
    "        satisfaction.sort()\n",
    "        dp = [[] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i] = [0] * (i + 2)\n",
    "        dp[0][1] = 1 * satisfaction[0]\n",
    "        for i in range(1,n):\n",
    "            for j in range(i + 2):\n",
    "                if j and j != i + 1:dp[i][j] = max(dp[i-1][j-1] + j * satisfaction[i],dp[i-1][j])\n",
    "                elif j == i + 1:dp[i][j] = dp[i-1][j-1] + satisfaction[i] * j\n",
    "                else:dp[i][j] = dp[i-1][j]\n",
    "        return max(dp[-1] + [0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        n = len(satisfaction)\n",
    "        satisfaction.sort()\n",
    "        dp = [[] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i] = [0] * (i + 2)\n",
    "        dp[0][1] = 1 * satisfaction[0]\n",
    "        for i in range(1,n):\n",
    "            for j in range(i + 2):\n",
    "                if j and j != i + 1:dp[i][j] = max(dp[i-1][j-1] + j * satisfaction[i],dp[i-1][j])\n",
    "                elif j == i + 1:dp[i][j] = dp[i-1][j-1] + satisfaction[i] * j\n",
    "                else:dp[i][j] = dp[i-1][j]\n",
    "        return max(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "#         satisfaction = sorted(satisfaction, reverse = True)\n",
    "\n",
    "#         presum = 0\n",
    "#         res = 0\n",
    "#         for i in satisfaction:\n",
    "#             if i + presum > 0:\n",
    "#                 presum += i\n",
    "#                 res += presum\n",
    "        \n",
    "#         return res \n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        satisfaction = sorted(satisfaction)\n",
    "        n = len(satisfaction)\n",
    "        dp = [[0 for _ in range(n+1)] for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1):\n",
    "                if i == j:\n",
    "                    dp[i][j] = dp[i-1][j-1] + satisfaction[i-1]*j\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+satisfaction[i-1]*j)\n",
    "        # print(dp)\n",
    "        return max(max(dp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "\n",
    "        satisfaction = sorted(satisfaction)\n",
    "\n",
    "        max_value = max(satisfaction)\n",
    "\n",
    "        if max_value < 0:\n",
    "            return 0\n",
    "\n",
    "        \n",
    "        \n",
    "        result = []\n",
    "        for i in range(len(satisfaction)):\n",
    "            time = 1\n",
    "            total = 0\n",
    "\n",
    "            for j in range(i, len(satisfaction)):\n",
    "                total += satisfaction[j] * time\n",
    "                time += 1\n",
    "                result.append(total)\n",
    "\n",
    "\n",
    "        return max(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        # DP[i][j]:前i个菜，选择其中的j个菜可以获得的最大满意度，j<=i\n",
    "        DP = [[0]*(len(satisfaction)+1) for _ in range(len(satisfaction)+1)]\n",
    "        satisfaction = sorted(satisfaction)\n",
    "        for i in range(1, len(satisfaction)+1):\n",
    "            for j in range(i+1):\n",
    "                if i==j:  # 说明遇到的每一个i都全选\n",
    "                    DP[i][j] = DP[i-1][j-1] + satisfaction[i-1]*j\n",
    "                elif j==0:\n",
    "                    DP[i][j] = 0\n",
    "                else:  # 选第i个菜 和 不选第i个菜\n",
    "                    DP[i][j] = max(DP[i-1][j-1]+satisfaction[i-1]*j ,DP[i-1][j])\n",
    "        ans = 0\n",
    "        for i in range(len(satisfaction)+1):\n",
    "            ans = max(ans, DP[len(satisfaction)][i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        # DP[i][j]:前i个菜，选择j个菜可以获得的最大满意度，j<=i\n",
    "        DP = [[0]*(len(satisfaction)+1) for _ in range(len(satisfaction)+1)]\n",
    "        satisfaction = sorted(satisfaction)\n",
    "        for i in range(1, len(satisfaction)+1):\n",
    "            for j in range(i+1):\n",
    "                if i==j:\n",
    "                    DP[i][j] = DP[i-1][j-1] + satisfaction[i-1]*j\n",
    "                elif j==0:\n",
    "                    DP[i][j] = 0\n",
    "                else:\n",
    "                    DP[i][j] = max(DP[i-1][j-1]+satisfaction[i-1]*j ,DP[i-1][j])\n",
    "        ans = 0\n",
    "        for i in range(len(satisfaction)+1):\n",
    "            ans = max(ans, DP[len(satisfaction)][i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        satisfaction.sort()\n",
    "        n = len(satisfaction)\n",
    "        dp = [[-10**20 for _ in range(n + 1)] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][1] = satisfaction[i]\n",
    "        for i in range(1, n):\n",
    "            for j in range(2, i + 2):\n",
    "                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + satisfaction[i] * j)\n",
    "        if max(dp[-1]) < 0:\n",
    "            return 0\n",
    "        return max(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        satisfaction.sort()\n",
    "        n = len(satisfaction)\n",
    "        dp = [[0]*(n+1) for _ in range(n+1)]#维度0表示做了几道菜，维度1表示最后做了哪道菜\n",
    "        dp[0][0] = 0\n",
    "        note = [-inf] *(n+1) #表示做了i道菜时的最大值\n",
    "        note[0] = 0\n",
    "        ans = 0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, i+1)[::-1]:\n",
    "                dp[j][i] = note[j-1] + j * satisfaction[i-1]\n",
    "                note[j] = max(dp[j][i], note[j])\n",
    "        return max(note)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, s: List[int]) -> int:\n",
    "        s.sort()\n",
    "        n = len(s)\n",
    "        f = [[float('-inf')] * (n+1) for _ in range(n+1)]\n",
    "        for i in range(n+1): f[i][0] = 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,i+1):\n",
    "                f[i][j] = max(f[i-1][j],f[i-1][j-1] + s[i-1] * j)\n",
    "        # print(f)\n",
    "        return max(f[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        satisfaction.sort()\n",
    "        n = len(satisfaction)\n",
    "        f = [[-inf]*(i+1) for i in range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            f[i][0] = 0\n",
    "            for t in range(1, i+1):\n",
    "                f[i][t] = f[i-1][t-1] + satisfaction[i-1]*t\n",
    "        return max(f[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        satisfaction.sort()\n",
    "        dp = []\n",
    "        for i in range(len(satisfaction)):\n",
    "            dp.append([0] * (i+2))\n",
    "            # if i == 0:\n",
    "            #     dp[i][0] = 0 \n",
    "            #     dp[i][1] = satisfaction[i] * 1\n",
    "            #     continue\n",
    "            s = satisfaction[i]\n",
    "            for o in range(i+2):\n",
    "                if o == 0:\n",
    "                    dp[i][0] = 0\n",
    "                    continue\n",
    "                elif i == 0:\n",
    "                    dp[i][o] = s\n",
    "                    continue\n",
    "                score = s * o + dp[i-1][o-1]\n",
    "                if o < i+1 and dp[i-1][o] > score:\n",
    "                    score = dp[i-1][o]\n",
    "                    \n",
    "                dp[i][o] = score\n",
    "      \n",
    "        return max(dp[len(satisfaction) - 1])\n",
    "                \n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "  \n",
    "\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        n = len(satisfaction)\n",
    "        f = [[0 for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "        satisfaction.sort()\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                a = f[i - 1][j]     #不选第i道菜\n",
    "                b = f[i - 1][j - 1] + satisfaction[i - 1] * j       #选第i道菜 \n",
    "                if i == j: f[i][j] = b\n",
    "                elif a > b: f[i][j] = a\n",
    "                else: f[i][j] = b\n",
    "        res = 0\n",
    "        # for i in range(0, n + 1):\n",
    "        #     for j in range(0, i + 1):\n",
    "        #         print(f[i][j], end=\",\")\n",
    "        #     print()        \n",
    "        for x in f[n]:\n",
    "            res = max(res, x)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        satisfaction.sort()\n",
    "        dp=[[0]*(len(satisfaction)+1) for _ in range(len(satisfaction)+1)]\n",
    "        dp[1][1]=satisfaction[0]\n",
    "        for i in range(2,len(satisfaction)+1):\n",
    "            for j in range(i+1):\n",
    "                if j==0:\n",
    "                    dp[i][j]=0\n",
    "                else:\n",
    "                    if i==j:\n",
    "                        dp[i][j]=dp[i-1][j-1]+j*satisfaction[i-1]\n",
    "                    else:\n",
    "                        dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+j*satisfaction[i-1])\n",
    "        return max(dp[len(satisfaction)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        n=len(satisfaction)\n",
    "        dp=[[float('-inf')]*(n+1) for i in range(n+1)]\n",
    "        dp[0][0]=0\n",
    "        satisfaction.sort()\n",
    "        for i in range(1,n+1):\n",
    "            dp[i][0]=0\n",
    "            for j in range(1,i+1):\n",
    "                dp[i][j]=max(dp[i-1][j-1]+satisfaction[i-1]*j,dp[i-1][j])\n",
    "        return max(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, sa: List[int]) -> int:\n",
    "        sa.sort()\n",
    "        n=len(sa)\n",
    "        dp=[[0]*(n+1) for _ in range(n)]\n",
    "        dp[0][0]=0\n",
    "        dp[0][1]=sa[0]\n",
    "        for i in range(1,n):\n",
    "            for j in range(1,i+2):\n",
    "                dp[i][j]=dp[i-1][j-1]+sa[i]*j\n",
    "        return max(dp[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        # 菜的长度\n",
    "        m = len(satisfaction)\n",
    "        dp = [[0] * 550 for _ in range(550)]\n",
    "        satisfaction.sort()\n",
    "        dp[1][0] = 0\n",
    "        dp[1][1] = satisfaction[0]*1\n",
    "\n",
    "        #dp[i][j]\n",
    "        #表示前i个物体中，选中j个菜，可以达到的最大值。\n",
    "        for i in range(2, m+1):\n",
    "            for j in range(i+1):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    if i == j:\n",
    "                        dp[i][j] = dp[i-1][j-1]+satisfaction[i-1] * j\n",
    "                    else:\n",
    "                        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+satisfaction[i-1] * j)\n",
    "        ans = max(dp[m])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        n = len(satisfaction)\n",
    "        satisfaction.sort()\n",
    "        print(satisfaction)\n",
    "        dp = [[0] + [-1001 ** 3] * (_ + 2) for _ in range(n)]\n",
    "        dp[0][1] = satisfaction[0]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, i + 2):\n",
    "                dp[i][j] = max(dp[i - 1][j - 1] + satisfaction[i] * (j), dp[i - 1][j])\n",
    "        for line in dp:\n",
    "            print(line)\n",
    "        return max(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        n = len(satisfaction)\n",
    "        satisfaction.sort()\n",
    "        print(satisfaction)\n",
    "        dp = [[0] + [-1001 ** 3] * (_ + 2) for _ in range(n)]\n",
    "        dp[0][1] = satisfaction[0]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, i + 2):\n",
    "                dp[i][j] = max(dp[i - 1][j - 1] + satisfaction[i] * (j), dp[i - 1][j])\n",
    "        for line in dp:\n",
    "            print(line)\n",
    "        return max(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        satisfaction.sort()\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        l = len(satisfaction)\n",
    "        # for i in range(l-1, -1, -1):\n",
    "        #     if s + satisfaction[i]>0:\n",
    "        #         s += satisfaction[i]\n",
    "        #         ans = ans+s \n",
    "\n",
    "        dp = [[0]*(l+1) for _ in range(l+1)]\n",
    "        # dp[0][0] = max(0, satisfaction[0])\n",
    "        ans = 0\n",
    "        for i in range(1,l+1):\n",
    "            for j in range(1, i+1):\n",
    "                dp[i][j] = dp[i-1][j-1]+satisfaction[i-1]*(j)\n",
    "                if i<j:\n",
    "                    dp[i][j] = max(dp[i][j] , dp[i-1][j])\n",
    "                ans = max(ans, dp[i][j])\n",
    "        # print(dp)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    动态规划版本，这个题目等价于0-1背包问题，在前i个菜中，选择j个，使得选中菜的价值总和最大\n",
    "    有个小点需要先想清楚，假设两道菜 a、b，价值0 < a < b，肯定a、b都选择的时候价值比不选要大，\n",
    "    那么是a->b的选择顺序还是b -> a的选择顺序呢？\n",
    "    a -> b 有 a + 2 * b\n",
    "    b -> a 有 b + 2 * a\n",
    "    由于a < b，所以 a + 2 * b > a + a + b = 2 * a + b，所以把大的放在后面会使得总价值更大\n",
    "    那么剩下的就是选和不选的问题了，选和不选就可以转化成0-1背包问题\n",
    "    '''\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        n = len(satisfaction)\n",
    "        '''\n",
    "        从小到大排序，保证大的在后面\n",
    "        '''\n",
    "        satisfaction.sort()\n",
    "        '''\n",
    "        可能不选，所以dp[i][j]定义为前i个元素，选择j - 1个元素的最大价值总和\n",
    "        初始时任何i个都可以不选，不选的总价值一定是0\n",
    "        '''\n",
    "        dp = [[float('-inf')] * (n + 1) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][0] = 0\n",
    "        dp[0][1] = satisfaction[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, i + 2):\n",
    "                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + satisfaction[i] * j)\n",
    "\n",
    "        return max(dp[-1][j] for j in range(n + 1))                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "#         satisfaction.sort()\n",
    "#         @cache \n",
    "#         def dp(i, time):\n",
    "#             if i >= len(satisfaction): return 0\n",
    "\n",
    "#             return max(\n",
    "#                 time * satisfaction[i] + dp(i + 1, time + 1),\n",
    "#                 dp(i + 1, time)\n",
    "#             )\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        n = len(satisfaction)\n",
    "        dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "        satisfaction.sort()\n",
    "        res = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                dp[i][j] = dp[i - 1][j - 1] + satisfaction[i - 1] * j\n",
    "                if j < i:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i - 1][j])\n",
    "                res = max(res, dp[i][j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        n = len(satisfaction)\n",
    "        satisfaction.sort()\n",
    "        # dp[i][j] 表示在前i道菜这选中j道菜时的最大喜爱时间\n",
    "        dp = [[0 for i in range(n + 1)] for _ in range(n + 1)]\n",
    "        res = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                # 第j次菜选择第i道菜（前面的肯定是i-1道中已经选中了j-1道）\n",
    "                dp[i][j] = dp[i - 1][j - 1] + j * satisfaction[i - 1]\n",
    "                # 每次选j道的值必定都比本i道中 或者 i-1道中选中的大\n",
    "                if j < i:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i - 1][j])\n",
    "                res = max(res, dp[i][j])\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        satisfaction.sort()\n",
    "        mem = []\n",
    "        for i in range(len(satisfaction)):\n",
    "            if (i == 0):\n",
    "                mem.append(satisfaction)\n",
    "            else:\n",
    "                mem.append([])\n",
    "        res = 0\n",
    "        for i in range(1,len(satisfaction)):\n",
    "            for j in range(len(satisfaction)):\n",
    "                if (i > j):\n",
    "                    mem[i].append(-1000000)\n",
    "                elif (i == j):\n",
    "                    mem[i].append(mem[i-1][j-1] + satisfaction[j]*(i+1))\n",
    "                elif (i < j):\n",
    "                    mem[i].append(max(mem[i][j-1], mem[i-1][j-1]+satisfaction[j]*(i+1)))\n",
    "                if mem[i][j] > res:\n",
    "                    res = mem[i][j]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        n = len(satisfaction)\n",
    "        satisfaction.sort()\n",
    "        dp = [[float('-inf')] * (n + 1) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][0] = 0\n",
    "        dp[0][1] = satisfaction[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, i + 2):\n",
    "                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + satisfaction[i] * j)\n",
    "\n",
    "        return max(dp[-1][j] for j in range(n + 1))                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfaction(self, satisfaction: List[int]) -> int:\n",
    "        n = len(satisfaction)\n",
    "        dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "        satisfaction.sort()\n",
    "        res = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                dp[i][j] = dp[i - 1][j - 1] + satisfaction[i - 1] * j\n",
    "                if j < i:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i - 1][j])\n",
    "                res = max(res, dp[i][j])\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
